/*
 * @Descripttion:
 * @version:
 * @Author: xiaozilai
 * @Date: 2022-10-30 20:38:44
 * @LastEditors: xiaozilai
 * @LastEditTime: 2022-10-30 20:48:23
 */
/*
 * @lc app=leetcode.cn id=784 lang=cpp
 *
 * [784] 字母大小写全排列
 *
 * https://leetcode.cn/problems/letter-case-permutation/description/
 *
 * algorithms
 * Medium (70.34%)
 * Likes:    468
 * Dislikes: 0
 * Total Accepted:    90.2K
 * Total Submissions: 125.3K
 * Testcase Example:  '"a1b2"'
 *
 * 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
 *
 * 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：s = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 *
 *
 * 示例 2:
 *
 *
 * 输入: s = "3z4"
 * 输出: ["3z4","3Z4"]
 *
 *
 *
 *
 * 提示:
 *
 *
 * 1 <= s.length <= 12
 * s 由小写英文字母、大写英文字母和数字组成
 *
 *
 */

// @lc code=start
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    vector<string> letterCasePermutation(string s) {
        vector<string> ans{};
        int n = s.length();
        backtracking(ans, s, 0, n);
        return ans;
    }

    void backtracking(vector<string> &ans, string &temp, int index, int n) {
        if (index >= n) {
            ans.push_back(temp);
            return;
        }
        if (isLetter(temp[index])) {
            temp[index] = exchange(temp[index]);
            backtracking(ans, temp, index + 1, n);
            temp[index] = exchange(temp[index]);
            backtracking(ans, temp, index + 1, n);
        } else {
            backtracking(ans, temp, index + 1, n);
        }
    }

    bool isLetter(char letter) {
        if ((letter <= 'Z' && letter >= 'A') || (letter <= 'z' && letter >= 'a')) {
            return true;
        } else {
            return false;
        }
    }
    char exchange(char letter) {
        if (letter <= 'Z' && letter >= 'A') {
            return letter + 'a' - 'A';
        } else {
            return letter + 'A' - 'a';
        }
    }
};
// @lc code=end
